package pro.softzhang.algo.lc200;

import pro.softzhang.algo.common.TreeNode;

/**
 *
 */
public class LC285_InorderSuccessorInBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2, new TreeNode(1, null, null), new TreeNode(3, null, null));
        TreeNode p = null;
        TreeNode r = new Solution1().inorderSuccessor(root, p);
        System.out.println(r == null ? null : r.val);
    }

    static class Solution {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            return root;
        }
    }

    /**
     * 充分利用BST的性质
     */
    static class Solution1 {
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
            TreeNode current = root, r = null;
            while (current != null) {
                if(current.val > p.val) {
                    r = current;
                    current = current.left;
                } else {
                    current = current.right;
                }
            }
            return r;
        }
    }
}